package com.lry.basic.algorithm.greedy;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/12/19
 */
public class MonotoneIncreasingDigits {
    public static void main(String[] args) {
        System.out.println(monotoneIncreasingDigits2(10));
    }

    public static int monotoneIncreasingDigits(int N) {
        if(isIncrease(N)){
            return N;
        }
        boolean f= false;
        String s = "";
        char[] nArr = (""+N).toCharArray();
        for(int i=0;i<nArr.length;i++){
            if(f){
                s+="9";
                continue;
            }
            if(i<nArr.length-1&&nArr[i]>nArr[i+1]){
                nArr[i]-=1;
                f = true;
            }
            s+=nArr[i];
        }
        if(s.startsWith("0")){
            s = s.substring(1);
        }
        return monotoneIncreasingDigits(Integer.parseInt(s));
    }

    private static boolean isIncrease(int n){
        char[] nArr = (""+n).toCharArray();
        for(int i=0;i<nArr.length-1;i++){
            if(nArr[i]>nArr[i+1]){
                return false;
            }
        }
        return true;
    }


    public static int monotoneIncreasingDigits2(int N) {
        char[] nArr = String.valueOf(N).toCharArray();
        int i = 1;
        while(i<nArr.length&&nArr[i-1]<=nArr[i]){
            i++;
        }

        while(i<nArr.length&&i>0&&nArr[i-1]>nArr[i]){
            nArr[i-1]--;
            i--;
        }
        for(int j=i+1;j<nArr.length;j++){
            nArr[j] = '9';
        }
        return Integer.parseInt(String.valueOf(nArr));
    }
}
